// 给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。

// 返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：

// 如果 S[i] == "I"，那么 A[i] < A[i+1]
// 如果 S[i] == "D"，那么 A[i] > A[i+1]
//  

// 示例 1：

// 输出："IDID"
// 输出：[0,4,1,3,2]

// 示例 2：

// 输出："III"
// 输出：[0,1,2,3]

// 示例 3：

// 输出："DDI"
// 输出：[3,2,0,1]
//  

// 提示：

// 1 <= S.length <= 1000
// S 只包含字符 "I" 或 "D"。

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<int> diStringMatch(string S) {
        int n{S.size()};
        int D{n}; // 遇D取最大
        int I{0}; // 遇I取最小
        vector<int> res(n+1);
        for (int i{0}; i < n; ++i) {
            if (S[i] == 'I') res[i] = I++;
            else if (S[i] == 'D') res[i] = D--;
        }
        res[n] = I;
        return res;
    }
};

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        vector<int> perm;
        int left = 0;
        int right = n;
        for (auto& c : s) {
            if (c == 'I') {
                perm.push_back(left++);
            } else if (c == 'D') {
                perm.push_back(right--);
            }
        }
        perm.push_back(left);
        return perm;
    }
};

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.length(), lo = 0, hi = n;
        vector<int> perm(n + 1);
        for (int i = 0; i < n; ++i) {
            perm[i] = (s[i] == 'I' ? lo++ : hi--);
        }
        perm[n] = lo; // 最后剩下一个数，此时 lo == hi
        return perm;
    }
};

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        vector<int> perm(n + 1);
        int left = 0;
        int right = n;
        for (int i = 0; i < n; ++i) {
            perm[i] = (s[i] == 'I' ? left++ : right--);
        }
        perm[n] = left;
        return perm;
    }
};
